In a digital color imaging system, a color image is represented as a set of color picture elements ("pixels"). Each pixel has associated with it a set of color values which describe the color (hue, saturation and lightness) for that position in the image. The color values correspond to the color coordinates in some given color space. There are many different color spaces (e.g. RGB, CIE tristimulus (XYZ), CIELAB, CIELUV, CMY(K), etc.) which are commonly used. Some color spaces, such as XYZ, CIELAB, and CIELUV are device independent and will therefore give an absolute measure of the color for each pixel in the image. Others, such as RGB and CMY(K), are device dependent and can only be related to an absolute color value if the spectral characteristics of a specific device are known.
For many applications it may be necessary to be able to take color image data from one device and display, manipulate, and/or print it on another device which may have very different spectral characteristics. For this reason, it is often necessary to be able to take image data in one color space, and convert it to a different color space. For example, it may be required to take RGB data from an input scanner and convert it to a device independent space such as CIELAB. This device independent data could then be used by a variety of different output devices which could then convert the data to their own device dependent color space for display. This permits the various devices to be calibrated so that the image will have the same color appearance regardless of what output device is used.
The transformation from one color system to another relates the coordinates in one space to those in a different color space. In some cases, this color transformation may be as simple as a matrix multiplication, as in the case of transforming from RGB to XYZ. In other cases the transformation is more complex, such as when transforming CIELAB into CMY(K).
In a digital imaging system there is always some precision loss associated with the quantization of color data, moreover additional precision losses can occur each time the image data is transformed or manipulated. As a result, there will be quantization errors associated with the color values (i.e., instead of a continuum of color levels, there are only a limited number of discrete levels which can be represented with a given digital precision.) Quantization errors manifest themselves as image artifacts. For example, if an original image contains a smooth color gradient, the quantized image will appear to have "contours." The visibility of these artifacts is a function of both the size of the color errors, and the sensitivity of the human observer to the errors. For example, in RGB space, an error in one of the components of a given magnitude will be much more noticeable for darker colors than for lighter colors. So-called "uniform color-spaces" (such as CIELAB) attempt to map the color values into a coordinate system where distance corresponds to perceived color differences. Although these spaces are actually not entirely uniform, they are significantly more uniform than linear spaces such as XYZ.
In many cases, a digital imaging system not only has different color spaces associated with different steps in the imaging chain, but there may also be different precision levels associated with the data at each step. For example, it may be necessary to reduce the number of digital levels in the data at some point in the process due to limitations on the number of bits which can be transmitted across some data path, or the memory size available for a look-up-table. Since the original quantized data must be resampled to reduce the number of color levels, this process can be called "secondary quantization."
The simplest way to reduce the number of digital levels is to resample the range of input levels linearly, (or equivalently to use only the most significant data bits). However, if this is done in a non-uniform color space such as RGB or XYZ, the errors introduced at the dark end of the input range may be quite objectionable, while the errors at the bright end of the input range may be so small that they are imperceptible. By using a non-linear mapping of the input to output levels it is possible to minimize the overall color error by balancing the perceived color errors over the color gamut. Logarithmic functions and various power laws, e.g. cube-root, etc., have been suggested as possible non-linear mapping functions in the past (M. I. Sezan, K. L. Yip and S. Daly, "Uniform perceptual quantization: applications to digital radiography," IEEE Trans. Sys. Man. Cyber. SMC-17, 622-634(1987)). Although these approaches are intuitively appealing because they attempt to model the non-linearity of the human observer, it can be shown they are not optimal. These approaches tend to over sample the darker end of the input range and usually result in under utilization of the possible output levels, i.e. input level 0 may map into output level 0, and input level 1 may map into output level 5 resulting in output levels 1 through 4 never being used. As a result, somewhere the color errors must be larger than necessary. This invention will map the input levels into a specified number of output levels in the optimum way so as to minimize the perceived color errors which are created by this secondary quantization process.
The problem of finding the best non-linear remapping has been addressed by Ray, Heckman, and Sullivan for the case of the optimum RGB secondary quantization for color soft video displays (L. Ray, C. Heckman and J. Sullivan, "Requantization of Color imagery," U.S. patent application Ser. No. 07/687,152). They show that the optimum non-linear secondary quantization function for reducing the number of digital levels in an RGB image can be determined by a global non-linear optimization technique.
This invention specifically addresses the problem of determining the optimum secondary quantization for the case of addressing a multi-dimensional color calibration table. This problem is important because many of the color space transformations which are necessary in a color digital imaging system are frequently implemented using a 3-dimensional look-up table (see U.S. Pat. No. 4,500,919). The memory requirements for the look-up table are directly related to the number of digital levels in the input color space. For example, if the input color space was RGB and the data was stored as 8-bit value (256 different levels) the look-up table would require 2.sup.3*8 (=2.sup.24 =16,777,216) different entries. If the color value stored at each address in the look-up table was given by three 8-bit output values this would imply that 48 MBytes of memory would be required to store the table. For many applications, this memory requirement may be impractical due to cost constraints. For this reason it is often necessary to reduce the number of levels in the input color data before addressing the color-calibration look-up table. For example, reducing the number of levels in the input data from 256 levels (8-bit addresses) to 64 levels (6-bit addresses) reduces the look-up table memory requirements from 48 MBytes to 786 KBytes. The output color corresponding to input colors which are intermediate to those stored in the look-up table can be generated by selecting the look-up table entry corresponding to nearest input color value, or by various methods of multi-dimensional interpolation (see U.S. patent application Ser. No. 07/696,299 entitled "System for performing Linear Interpolation" by G. Newman). The method which is used to quantize the input color space to the smaller number of levels dramatically effects the perception of color artifacts generated by the system. This is true whether nearest-neighbor selection or more sophisticated methods of multi-dimensional interpolation are used.
The present invention is significantly different from the earlier invention of Ray et. al., in several respects. In the case of Ray, et. al., the color data exists in a specific color space and the desired goal is to reduce the precision of that data while reining in the same color space. In this case, the goal is to convert the data from an initial color space into a different color space using an intermediate multi-dimensional look-up table. The reduction in the precision of the data is therefore not an end, but a means. Another major difference is that in the case of Ray, et. al., the individual components of the color value are considered independently, although the color errors are computed from the combined values. In the present invention, the different color components are correlated in the sense that each position in the multi-dimensional look-up table is addressed by all of the components in the input space.